/*
 * Copyright (c) 1995-2009
 *     J.J. Lukkien
 *     Department of Mathematics and Computer Science
 *     Eindhoven University of Technology
 *     P.O. Box 513
 *     5600 MB Eindhoven, The Netherlands
 *
 * File:    random.c
 * Version: derived from RCS
 *
 *  Source code for random generator described in
 *      The Stanford GraphBase, A platform for Combinatorial Computing,
 *      by Donald Knuth.
 */

#define two_to_the_31 ((unsigned int) 0x80000000)

/* Macro for difference modulo 2^31: */
#define mod_diff( x, y ) (((x) - (y)) & 0x7fffffff)
#define random()   ( *gb_fptr >= 0 ? *gb_fptr-- : gb_flip_cycle () )

static int A[56] = { -1 };  /* Stores 55 pseudo-random values */

int *gb_fptr = A;           /* The next value of A to be exported */

int gb_flip_cycle ( void )
  {
   register int *ii, *jj;

   for ( ii = &A[1], jj = &A[32]; jj <= &A[55]; ii++, jj++ )
     *ii = mod_diff( *ii, *jj );
   for ( jj = &A[1]; ii <= &A[55]; ii++, jj++ )
     *ii = mod_diff ( *ii, *jj );
   gb_fptr = &A[54];
   return A[55];
  }

void initrandom ( int seed )
  {
   register int i;
   register int prev = seed, next = 1;

   seed = prev = mod_diff ( prev, 0 );  /* Strip off the sign */
   A[55] = prev;
   for ( i = 21; i; i = (i+21) % 55 )
     {
      A[i] = next;

      /* Compute a new next value, based on next, prev, and seed */

      next = mod_diff ( prev, next );
      if ( seed & 1 )
	seed = 0x40000000 + ( seed >> 1 );
      else
	seed >>= 1;
      next = mod_diff ( next, seed );

      prev = A[i];
     }

   /* Get the array values "warmed up" */

   (void) gb_flip_cycle ();
   (void) gb_flip_cycle ();
   (void) gb_flip_cycle ();
   (void) gb_flip_cycle ();
   (void) gb_flip_cycle ();
  }

int unifrandom ( int m )
  {
   register unsigned int t
     = two_to_the_31 - ( two_to_the_31 % m );
   register int r;

   do
     {
      r = random ();
     }
     while ( t <= (unsigned int) r );

   return r % m;
  }

